package com.cheng.learn.leetcode;

/**
 * @description: 在排序数组中查找元素的第一个和最后一个位置
 * @author: ChengHaiZhu
 * @create: 2021-03-16 22:56
 **/
public class SearchRange34 {
    /**
     * 二分法查找： 力扣第34道题
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        if(right == 0 && nums[0] == target){
            return new int[]{0,0};
        }
        while (left <= right){
            int mid = (left + right)/2;
            if (nums[mid] == target){
                left = mid;
                right = mid;
                while(left >= 0 && nums[left] == target){
                    left --;
                }
                while(right <= nums.length - 1 && nums[right] == target){
                    right ++;
                }
                return new int[]{left + 1,right - 1};
            } else if(nums[mid] > target){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return new int[]{-1,-1};
    }
}
